package com.mokairui.sort.base;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * @Description 选择排序 时间复杂度 O(n^2)
 * @Author Mokairui
 * @Since 2021/10/7
 */
@Slf4j(topic = "c.selection")
public class Selection {
    public static void main(String[] args) {
        Integer[] arr = {4, 5, 6, 3, 2, 1};
        Bubble.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 对数组arr进行排序
     */
    public static void sort(Comparable[] arr) {
        for (int i = 0; i < arr.length - 2; i++) {
            // 定义一个变量, 记录最小元素所在的索引, 默认为参与选择排序的第一个元素所在的位置
            int minIndex = i;
            for (int j = 0; j < arr.length; j++) {
                // 需要比较最小索引 minIndex 处的值和 j 索引位置的值
                if (greater(arr[minIndex], arr[j])) {
                    minIndex = j;
                }
            }
            // 交换最小元素所在索引 minIndex 处的值和索引 i 处的值
            exch(arr, minIndex, i);
        }
    }

    /**
     * 比较v元素和m元素的大小
     */
    public static boolean greater(Comparable v, Comparable m) {
        return v.compareTo(m) > 0;
    }

    /**
     * 交换元素位置
     */
    public static void exch(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
